【题解】[NOIP模拟 9.17]灰狼呼唤着同胞

发表于 | 分类于 | 误人子弟 个
字数统计: 1,334 | 阅读时长 ≈ 6

诈尸了…这题比较 容易口胡 有意思，所以…

题目描述

我的母亲柯蒂丽亚，是一个舞者。身披罗纱，一身异国装扮的她，来自灰狼的村子。

曾经在灰狼村子担任女侍的她，被认定在某晚犯下可怕的罪行之后，被赶出了村子。

一切的元凶，都要回到母亲犯下重罪的那一晚。

我不认为柯蒂丽亚有犯罪。

二十年前的混沌，一共有n块碎片。

这n块碎片曾经两两之间都有联系，可是很多联系都在时间的洪流中消失了。

现在，我只能确定其中 m 条联系的种类。

每条联系都是一条无向边，任意两块碎片之间至多有一条联系，没有联系会连接在同一块碎片的两端。

联系有两种。一种是冲突，用0表示；另一种是吻合，用1表示。

虽然已经过去了二十年，但是联系的种类是不会变的。

现在，我想要用这 m 条联系，去推断二十年前的 n(n-1)/2 条联系的种类。

如果我推理出所有联系的种类，那么我就可以将混沌言语化，证明柯蒂丽亚的清白。

在灰狼的村子，我得知了推理的唯一条件：

二十年前，对于任意三块互不相同的碎片，要么这三块碎片两两吻合，要么恰好有一对碎片互相吻合。

我想要知道，二十年前n块碎片两两之间的联系，可能有多少种。

你只要输出方案数模 998244353 之后的结果。如果已经确定的m条联系不符合上述条件，请输出 0。

两种方案不同，当且仅当存在两块碎片，在一种方案中冲突，在另一种方案中吻合。也就是说，你要求的是有多少种可能的原图。

输入

第一行两个整数 Test,T，Test 表示测试点的编号，T 表示数据的组数。保证 T≤3。

接下来 T 组数据，每组数据第一行两个整数 n,m，

接下来 m 行，每行三个整数 u,v,t，表示第 u 块碎片和第 v 块碎片之间联系的种类为 t。

输出

共T行，每行一个整数，表示方案数对 998244353 取模后的结果。

样例输入：

0 2
3 0
4 2
1 2 1
1 3 0

样例输出：

4
2

样例解释

第一组数据中，三块碎片两两吻合的方案有 1 种，三块碎片中恰好有一对碎片互相吻合的
方案有 3 种，总共有 4 种方案。

第二组数据中，因为第 1、2 块碎片吻合，第 1、3 块碎片冲突，所以第 2、3 块碎片一定
冲突。

解题思路

先按题意建边并分类标号，若不合法，则标记退出。统计连通块个数。
将点染色。
只要确定任意连通块内的任意一点，那个连通块内所有点都将被确定（敌人的敌人就是朋友）。
即所有点都将被染成黑白两色。
这个连通块与另一个连通块间的连边种类（冲突 or 吻合），将确定另一个连通块的所有点的颜色。
以此类推，
最后两个连通块间的边将由点的颜色确定，即连边方案数为 2 ^ (连通块个数 - 1)。
得出答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <cmath>
#define re register long long
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define drep(i,a,b) for(re i=a;i>=b;--i)
typedef long long ll;
using namespace std;
inline ll read(){
    ll x=0;bool f=0;char ch=getchar();
    while(!isdigit(ch)) f^=!(ch^'-'),ch=getchar();
    while(isdigit(ch)) x=((x+(x<<2))<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}
inline void Online_Judge(){
    #ifndef ONLINE_JUDGE
        freopen("brethren.in","r",stdin);
        freopen("brethren.out","w",stdout);
    #endif
}
ll Test,T;
ll head[100050],to[2000050],nxt[2000050],cnt,ans;
bool f[2000050],vis[100050],color[100050],rflag;
inline void addedge(ll u,ll v,bool flag){
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
    f[cnt]=flag;
}
inline void dfs(ll x){
    vis[x]=1;
    for(ll i=head[x];i;i=nxt[i]){
        ll too=to[i];
        if(vis[too]==1){
            if(f[i]==0 and color[x]==color[too]) rflag=1;//判合法操作
            if(f[i]==1 and color[x]!=color[too]) rflag=1;
        }
        else{
            if(f[i]==0) color[x]==1?color[too]=0:color[too]=1;//染色操作
            if(f[i]==1) color[x]==1?color[too]=1:color[too]=0;
            dfs(too);
        }
    }
}
int main(){
//    Online_Judge();
    Test=read(),T=read();
    while(T--){
        memset(head,0,sizeof head);
        memset(to,0,sizeof to);
        memset(nxt,0,sizeof nxt);
        memset(f,0,sizeof f);
        memset(vis,0,sizeof vis);
        memset(color,0,sizeof color);//咳咳
        cnt=0,ans=0,rflag=0;
        ll n=read(),m=read();
        rep(i,1,m){
            ll u=read(),v=read();
            bool t;
            cin>>t;
            addedge(u,v,t);
            addedge(v,u,t);
        }
        rep(i,1,n){
            if(vis[i]==1) continue;
            ans++;
            dfs(i);
        }
        if(rflag==1){
            puts("0");
            continue;
        }
        ll anss=1;
        rep(i,1,ans-1){
            anss<<=1;
            anss%=998244353;
        }
        printf("%lld\n",anss);
    }

    return 0;
}

题目来源

cxslzxOJ 1501 灰狼呼唤着同胞（常州2017提高day6第2题）

0%